 \chapter[Sterowanie drużyną w lidze \w{Small Size}]{Sterowanie drużyną w lidze\\ \w{Small Size}}


 Sprawna gra robotów w piłkę nożną jest zadaniem złożonym i wymaga
 rozwiązaniu szeregu problemów z dziedziny sterowania oraz modelowania.
 Robot musi być w stanie poruszać się bezkolizyjnie w środowisku, które
 ulega ciągłym, dynamicznym zmianom. W tym celu niezbędna jest
 implementacja odpowiednich algorytmów unikania przeszkód i wyznaczania
 trasy, które są w stanie uwzględnić wpływ zmieniającego się stanu gry.
 Oprócz tej umiejętności skuteczna drużyna \rc{} musi grać zespołowo -
 do tego konieczny jest podział zadań oraz planowanie strategii gry.
 Nie można również pominąć faktu, iż wszystkie akcje podejmowane na
 boisku spotykają się z reakcją przeciwnika, która może uniemożliwić
 naszej drużynie realizację celów. Praca w tak złożonej domenie jak
 \rc{} wymaga więc stosowania usystematyzowanego opisu.


 \section{Zawodnik jako agent}


 Popularnym podejściem stosowanym w robotyce jest traktowanie robota
 jako \w{agenta upostaciowionego}. Stan agenta w systemie
 wieloagentowym określany jest poprzez zestaw czterech parametrów:
 \begin{description}
 \item[stan systemu sterującego agentem (C)] - oznaczający wartości
 zmiennych programu, zawartość rejestrów itp.,
 \item[stan efektorów agenta (E)] - określający aktualne położenie
 elementów wykonawczych pozwalających na interakcję z otoczeniem
 (silników, manipulatorów~itp.),
 \item[aktualne odczyty \w{czujników wirtualnych} (V)] - agregują one
 odczyty jednego lub większej liczby czujników rzeczywistych agenta,
 \item[stan transmisji (T)] - składający się z informacji odebranych
 lub nadanych do innych agentów.
 \end{description}
 Komponenty agenta są wykorzystywane przez system sterujący w celu
 realizacji konkretnego zadania. Sterowanie odbywa się dwuetapowo. Etap
 pierwszy to gromadzenie informacji, realizowane poprzez:
 \begin{itemize}
 \item pobranie aktualnych odczytów z zestawu czujników,
 \item odebranie informacji od innych agentów,
 \item sprawdzenie stanu własnych efektorów agenta.
 \end{itemize}
 Na podstawie tych danych oraz informacji zapisanej w formie zmiennych
 programu system sterujący agentem:
 \begin{itemize}
 \item ustawia pożądany stan efektorów,
 \item dokonuje konfiguracji sensorów,
 \item przesyła informacje do pozostałych agentów,
 \item zapisuje potrzebne informacje o stanie.
 \end{itemize}
 Podstawowa klasyfikacja agentów upostaciowionych bazuje na posiadanych
 przez nie komponentach. Wyróżniamy następujące rodzaje agentów:


 \begin{tabular}{l l}
 \toprule
 \bfseries rodzaj agenta & \bfseries komponenty \\
 \toprule
 upostaciowiony o pełnej funkcjonalności & CEVT \\
 \midrule
 autonomiczny, niezdolny do komunikacji & CEV \\
 \midrule
 niezdolny do poruszania się (np. zdalny sensor) & CVT \\
 \midrule
 sterowany zdalnie, nie posiada sensorów & CET \\
 \midrule
 pozbawiony sensorów oraz możliwości komunikacji & CE \\
 \midrule
 monitorujący (np. czarna skrzynka) & CV \\
 \midrule
 agent wykonujący obliczenia (koordynator) & CT \\
 \midrule
 agent zombie (nieprzydatny) & C \\
 \bottomrule
 \end{tabular}

\vspace{0.5cm}

\noindent
 Stosując powyższy podział do ligi małych robotów można zauważyć, iż w
 rozgrywkach \w{Small Size} biorą udział dwa rodzaje agentów:
 \begin{enumerate}
 \item agent typu CT - działający poza boiskiem koordynator, do którego
 spływają informacje z systemu wizyjnego i który na ich podstawie
 oblicza sterowania dla zawodników na boisku,
 \item agent typu CET - sterowany zdalnie agent na boisku, otrzymujący
 polecenia od agenta--koordynatora.
 \end{enumerate}


 \section{Systemy wieloagentowe}


 W przypadku, gdy minimum dwa roboty działają w tym samym środowisku i
 możliwa jest interakcja między nimi, mamy do czynienia z tzw.
 \w{systemem wieloagentowym} (lub \w{wielorobotowym}). Zastosowanie
 takiego systemu niesie ze sobą szereg korzyści. Grupa współpracujących
 robotów:
 \begin{itemize}
 \item jest w stanie realizować zadania zbyt złożone dla jednego robota,
 \item poprzez odpowiedni podział obowiązków może wykonywać zadania
 szybciej niż pojedynczy robot,
 \item pozwala na uproszczenie konstrukcji (grupa prostych robotów może
 być łatwiejsza w budowie niż jeden uniwersalny, realizujący to samo
 zadanie),
 \item jest bardziej niezawodna - w razie awarii roboty mogą siebie
 zastępować, łatwiej też wymienić jeden element systemu,
 \item pozwala na współdzielenie zasobów - roboty mogą np. korzystać ze
 wspólnego zestawu narzędzi lub akcesoriów.
 \end{itemize}
 Biorąc pod uwagę strukturę organizacyjną systemu wieloagentowego,
 można wyróżnić systemy:
 \begin{description}
 \item[scentralizowane] - o strukturze globalnej, w której zadania są
 wyznaczane robotom poprzez nadrzędnego koordynatora; są to przeważnie
 systemy hierarchiczne,
 \item[rozproszone] - o strukturze lokalnej, nie posiadającej jednostki
 centralnej; współpraca i realizacja celów przez roboty w tym systemie
 wynika z~reguł, które zostały im wbudowane.
 \end{description}
 W systemach wieloagentowych wyróżnia się dwa rodzaje komunikacji:
 \begin{description}
 \item[jawna] - informacje o stanie są wymieniane pomiędzy robotami,
 \item[niejawna] - nie ma przekazu danych, wszelkie informacje bazują
 na obserwacji otoczenia.
 \end{description}
 Łącząc strukturę organizacyjną oraz sposób komunikacji, otrzymujemy
 następujące rodzaje systemów wieloagentowych:
 \begin{description}
 \item[hierarchiczne] - współpraca agentów jest koordynowana globalnie,
 komunikacja jest jawna,
 \item[reaktywne] - o strukturze rozproszonej; każdy z robotów ma
 wbudowany prosty zestaw reguł (na zasadzie bodziec--reakcja), z
 których wynika współpraca w systemie; nie ma jawnej komunikacji,
 \item[behawioralne] - podobnie jak w przypadku systemu reaktywnego,
 systemy o rozproszonej strukturze i braku komunikacji; sterowniki
 robotów posługują się bazą złożonych działań zwanych \w{zachowaniami},
 które mogą być wykonywane równolegle,
 \item[peer-to-peer] - o strukturze lokalnej, ale roboty mogą
 komunikować się między sobą bezpośrednio.
 \end{description}


 \section{Przegląd istniejących rozwiązań\label{sec:przeglad}}


 Procedura zgłaszania zespołu do zmagań ligi małych robotów wymaga od
 jego twórców przygotowania publicznej dokumentacji, opisującej w
 skrócie zastosowane rozwiązania - zarówno w dziedzinie konstrukcji
 mechanicznej, jak i oprogramowania zawodników. Dzięki temu możliwy był
 przegląd aktualnego stanu wiedzy i rozpoznanie technik, które z
 powodzeniem sprawdzają się z środowisku ligi \w{Small Size}. Podczas
 analizy skupiono się na dwóch obszarach: sposobach bezkolizyjnej
 nawigacji oraz algorytmach sterowania grą drużyny. Przegląd oparto na
 dokumentach opublikowanych przez drużyny startujące w zawodach
 \w{RoboCup 2010}, zwracając szczególnie uwagę na najlepsze zespoły
 (\w{SKUBA} z Tajlandii \cite{skuba}, \w{CMDragons} z USA \cite{cmdragons} oraz
 \w{MRL} z Iranu \cite{mrl}).


 \subsection{Architektura systemu}

 Analizując dokumentację wspomnianych zespołów można zauważyć, iż
 używają one podobnych rozwiązań w kwestii sterowania grą. W lidze
 \w{Small Size} dominują złożone systemy hybrydowe, o scentralizowanej
 strukturze i elementach behawioralnych (roboty korzystają z bazy
 predefiniowanych \textit{zachowań} do wykonywania zadań). W systemach
 tych globalny koordynator zarządza grą drużyny tworząc z prostych
 zachowań przydzielonych robotom złożone i~długofalowe strategie dla
 całego zespołu, prowadzące do osiągnięcia wspólnego celu - wygrania
 meczu. Podobnie rozwiązana jest też kwestia podziału na moduły
 funkcjonalne systemu (wynika to ze sposobu komunikacji oraz pobierania danych, narzuconego przez reguły ligi). Mamy zatem moduł
 przetwarzania obrazu, który analizuje dane z kamery oraz generuje
 informacje o położeniu piłki i robotów. Dane te, wzbogacone o
 aktualne komendy sędziego, trafiają do bloku modelującego stan gry.
 Jego zadaniem jest m. in. filtracja zaszumionych danych o rozgrywce
 oraz predykcja możliwych położeń obiektów w następnym kroku działania
 algorytmu (należy tutaj brać pod uwagę fakt, iż cały cykl pobierania
 danych, obliczania sterowań oraz wysłania sygnałów sterujących 
 wprowadza ok. $100~ms$ opóźnienia, którego nie można pominąć w
 procesie decyzyjnym). Obliczane są także wysokopoziomowe predykaty
 określające, która z drużyn jest w posiadaniu piłki, kto atakuje, w
 jakich rolach występują roboty na boisku itp. Następnie informacja
 zawarta w bloku modelującym jest przetwarzana przez blok
 odpowiedzialny za strategię drużyny, który przydziela zadania robotom.
 Jeżeli związane są one z przemieszczaniem się po boisku, blok
 nawigacyjny wyznacza bezkolizyjną ścieżkę dla zawodnika prowadzącą do
 zadanego punktu. Ścieżka ta podlega przetworzeniu przez blok
 kontrolera ruchu robota, który oblicza odpowiednie
 wartości prędkości liniowych oraz kątowej $(v_x,v_y,\omega)$, z jakimi
 powinien poruszać się zawodnik. Taka informacja jest wysyłana do
 robota, gdzie przeliczana jest ona na bezpośrednie wartości sterowań
 zadawane silnikom. Schemat architektury systemu przedstawiono na
 rysunku~\ref{fig:architektura_stp}.

      \begin{figure}[!t]
      \centering
      \includegraphics[width=0.9\textwidth]{./architektura_stp}
      \caption{Schemat architektury systemu sterującego rozgrywką\\ w lidze \w{Small Size}\label{fig:architektura_stp}}
      \end{figure}

 \subsection{Sterowanie grą drużyny}


 Najważniejszym elementem architektury systemu sterowania jest moduł
 generujący strategię gry drużyny. Kluczowym wymaganiem stawianym temu
 komponentowi jest możliwość kontrolowania zespołu robotów w taki
 sposób, aby maksymalizować ilość strzelonych bramek przy jednoczesnym
 minimalizowaniu ilości goli straconych. Skuteczny algorytm pozwala na
 sprawne koordynowanie działań robotów, a także na szybkie reakcje na
 zmiany sytuacji na boisku oraz na trudne do przewidzenia zachowania
 przeciwników. Struktura oprogramowania musi być odpowiednio
 zaprojektowana, aby umożliwić łatwe modyfikacje oraz dodawanie nowych
 komponentów.


 Stosowane algorytmy sterowania rozgrywką ewoluowały wraz z rozwojem
 ligi \w{Small Size}. Obecnie dominują rozwiązania oparte na
 koncepcji STP, opracowanej i zastosowanej po raz pierwszy przez
 drużynę \w{CMDragons} w 2004 roku \cite{stp}. Podejście to
 potwierdziło swoją skuteczność w rozgrywkach i stało się punktem
 wyjścia dla zaproponowanego w niniejszej pracy algorytmu, dlatego też
 zdecydowano się na jego szczegółowy opis.


 \subsubsection{Skills, Tactics and Play (STP)}
 Skrót STP oznacza trzy komponenty, na których oparte jest sterowanie
 drużyną robotów:
 \begin{itemize}
 \item \textbf{zachowania (skills)}, definiujące podstawowe
 umiejętności robota, takie jak jazda do zadanego celu czy obrót z
 piłką,
 \item \textbf{taktyki (tactics)}, jakimi może posługiwać się zawodnik,
 definiujące konkretny zestaw zachowań, których należy użyć np. w celu
 oddania strzału na bramkę przeciwnika,
 \item \textbf{plany gry (play)}, posiadające warunki wykonalności i
 zakończenia; definiujące zestaw taktyk, jakimi powinny posługiwać się
 poszczególne roboty dla konkretnej sytuacji na boisku.
 \end{itemize}


 W każdej iteracji algorytmu, która rozpoczyna się wraz z nadejściem nowych
 danych z kamery, następuje wybranie najodpowiedniejszego planu gry do
 wykonania w danej sytuacji. Na jego podstawie wyznaczane są taktyki
 dla poszczególnych robotów. Wybrana taktyka definiuje zachowanie,
 jakie powinno zostać wykonane przez robota w danej chwili. Wykonywanie
 planu może trwać od $5$ do $30~s$. Taktyki trwają zwykle ok. $1-30~s$, a
 pojedyncze zachowania cechują czasy wykonania w przedziale $300~ms-5~s$.


 Bardziej formalny opis przedstawia plan \emph{P} jako ustalony wariant
 gry, z~konkretnym zestawem warunków wykonalności oraz zakończenia,
 posiadający zbiór \emph{N} ról, po jednej dla każdego zawodnika w
 drużynie. Role przydzielane są dynamicznie podczas gry. Każda z nich
 składa się z sekwencji $T^1,T^2,...$ taktyk oraz przypisanych do nich
 parametrów. Taktyki stanowią tym samym elementarne akcje pozwalające
 wpływać na stan gry (z perspektywy planu). Ze względu na kontakt
 zawodnika z piłką taktyki można podzielić na aktywne oraz pasywne. W
 danej sekwencji w planie wykonywana jest tylko jedna taktyka aktywna.
 Jej zakończenie powoduje przejście do kolejnej sekwencji planu.


 Taktyka $T_i$ opisuje konkretny ciąg zachowań robota $i$. Zdefiniowany
 jest on za pomocą maszyny stanów $SSM_i$. Zawiera ona zestaw
 elementarnych akcji, które muszą zostać wykonane w celu zrealizowania
 taktyki. Ponadto jeżeli mamy do czynienia z taktyką aktywną,
 zdefiniowane są dla niej warunki zakończenia określające jej
 powodzenie. Zachowania $S$ mogą wchodzić w skład jednej lub większej
 liczby maszyn stanów. Przejścia między stanami zdefiniowane są w
 zależności od sytuacji w grze, czasu wykonywania danego zachowania
 oraz taktyki, w której skład wchodzą.


 \begin{algorithm}[!b]
 \caption{Główny algorytm STP}
 \label{alg:STP}
 \begin{algorithmic}[1]
 \STATE CaptureSensors()
 \STATE RunPerception()
 \STATE UpdateWorldModel()
 \STATE $P \leftarrow $ ExecutePlayEngine()
 \FORALL { robot $i \in (1,...,N)$}
        \STATE $(T_i,TParams_i) \leftarrow \text{GetTactic}(P,i)$
        \STATE $(SSM_i,SParams_i) \leftarrow \text{ExecuteTactic}(T_i,TParams_i)$
        \IF {$\text{NewTactic}(T_i)$}
                \STATE $S_i \leftarrow SSM_i(0)$
        \ENDIF
        \STATE $(command_i, S'_i) \leftarrow \text{ExecuteStateMachine}(SSM_i,S_i,SParams_i)$
        \STATE $robot\_command_i \leftarrow \text{ExecuteRobotControl}(command_i)$
        \STATE $\text{SendCommand}(i,robot\_command_i)$
 \ENDFOR
 \end{algorithmic}
 \end{algorithm}


 Plany gry, taktyki oraz zachowania tworzą hierarchiczną strukturę
 sterowania zespołem robotów. Plany kontrolują sposób gry drużyny
 poprzez taktyki, podczas gdy taktyki opisują złożone akcje wykonywane
 przez roboty za pomocą podstawowych zachowań. Zachowania te
 przekładają się na konkretne sygnały sterujące wysyłane do robotów.
 Mechanizm działania STP można zapisać w sposób uproszczony za pomocą
 algorytmu \ref{alg:STP}.

 \subsubsection{Taktyki}

 Dla sterowania pojedynczym robotem istotne są taktyki oraz zachowania.
 Na potrzeby implementacji algorytmu STP stworzono zbiór taktyk
 aktywnych (związanych z operowaniem piłką) oraz pasywnych. Właściwości taktyk zostały sparametryzowane,
 co pozwoliło za pomocą ich niewielkiego zestawu opisać złożony zbiór zachowań robotów na boisku. Część
 taktyk wraz z parametrami przedstawiono w tabeli \ref{tab:taktyki_STP}. 

 \begin{table}[!b]
 {
 \centering
 \footnotesize
 \begin{tabular}{|l|l|}
 \hline
 \multicolumn{1}{|c}{\textbf{taktyki aktywne}} &
 \multicolumn{1}{|c|}{\textbf{taktyki pasywne}} \\
 \hline
 strzelaj(celowanie\textbar bez celowania) & pozycja     do przechwycenia
 piłki(region)\\
 aktywna obrona(punkt) & pozycja do odbicia piłki(region) \\
 drybluj do strzału(region) & pozycja do podania piłki(region)   \\
 drybluj do regionu(region) & broń linii (współrzędne, min. odległość)    \\
 pozycja do wznowienia gry(punkt,rotacja) & broń punktu(punkt, min. odległość)\\
 pozycja do strzału & broń pasa(punkt1, punkt2)\\
 pozycja do rzutu karnego & kryj (piłka\textbar bramka\textbar strzał)\\
 odbierz podanie & bramkarz\\
 przechwyć piłkę & stój  \\
 \hline
 \end{tabular}
 \caption{Taktyki stosowane w STP \label{tab:taktyki_STP}}
 }
 \end{table}


 Przykładem realizacji taktyki jest algorytm \ref{alg:strzelaj}.
 Przedstawia on sekwencję warunków oraz zachowań stosowaną podczas
 oddawania strzału. Ważnym elementem jest moduł oceny, który stosując
 pewną heurystykę pozwala określić, które z akcji będą korzystniejsze w
 danej sytuacji. W tym przypadku analizowane są możliwości oddania
 strzału bezpośrednio na bramkę oraz strzału w stronę partnera, który
 byłby w stanie od razu skierować piłkę do bramki (tzw. ,,gra z
 klepki''). Jeżeli wartość oceny żadnej z wyżej wymienionych opcji nie
 przekroczy pewnego minimalnego progu, robot skieruje się w stronę
 miejsca, z którego będzie miał większe szanse na skuteczny strzał. W
 tym przypadku używana jest maszyna stanów o nazwie
 \texttt{MoveBall}, której działanie parametryzowane jest
 współrzędnymi celu oraz flagą decydującą o tym, czy robot powinien
 oddać strzał.

 \begin{algorithm}[!t]
 \caption{Taktyka \texttt{shoot(i)}}  
 \label{alg:strzelaj}
 \begin{algorithmic}[1]
 \STATE $bestScore \leftarrow 0$
 \STATE $(score,target) \leftarrow$ evaluation.aimAtGoal()
 \STATE $SParam_i \leftarrow $ setCommand(MoveBall,target,KICK\_IF\_WE\_CAN)
 \STATE $bestScore \leftarrow score$


 \FORALL {teammate $j$}
        \IF {evaluation.deflection($j$) $ >$ THRESHOLD}
                \STATE $(score,target) \leftarrow$ evaluation.aimAtTeammate($j$)
                \IF {$score > bestScore$}
                        \STATE $SParam_i \leftarrow $ setCommand(MoveBall,target,KICK\_IF\_WE\_CAN)
                        \STATE $bestScore \leftarrow score$
                \ENDIF
        \ENDIF
 \ENDFOR


 \IF {\w{no\_target\_found} \textbf{or} $score < $ THRESHOLD}
        \STATE $target \leftarrow $ evaluation.findBestDribbleTarget()
        \STATE $SParam_i \leftarrow $ setCommand(MoveBall,target,NO\_KICK)
 \ENDIF
 \end{algorithmic}
 \end{algorithm}


 \subsubsection{Zachowania}


 Jak można zauważyć, skuteczne wykonanie taktyki wymaga zdefiniowania
 pewnego ciągu zachowań robota. Może on zależeć od aktualnego stanu
 gry. Przykładowo, jeżeli robot ma za zadanie przemieścić piłkę w stronę
 środka boiska, wymaga to wykonania sekwencji zachowań:
 \begin{enumerate}
 \item podjechanie do piłki,
 \item przechwycenie piłki za pomocą \w{dribblera},
 \item obrócenie piłki w kierunku środka boiska,
 \item pchanie piłki w stronę celu z włączonym \w{dribblerem}.
 \end{enumerate}
 Inna sekwencja realizująca ten sam cel będzie użyta w przypadku, gdy piłka znajduje się w narożniku boiska - 
 wtedy robot nie może się z~nią obracać, aby nie wyjechać poza pole gry - konieczne będzie
 przesunięcie się z piłką w taki sposób, aby mieć więcej przestrzeni do
 manewrowania, co stanowi dodatkowe zachowanie do wykonania.


 Twórcy STP stworzyli cały szereg zachowań potrzebnych w specyficznych
 sytuacjach, z~którymi robot ma do czynienia na boisku. Algorytm
 każdego z~zachowań składa się z fazy przetwarzania danych z czujników,
 generowania sterowań dla efektorów oraz przejścia do kolejnego (lub
 tego samego) zachowania wynikającego z taktyki przy spełnieniu
 określonych warunków (np. czasu trwania danego zachowania, stanu
 posiadania piłki itd.). Warunki te są określane jako parametry maszyny
 stanów, w której skład wchodzi dane zachowanie - dzięki temu możliwe
 jest ponowne użycie kodu danego zachowania w innej taktyce (z innymi
 parametrami).


 Sposób realizacji zachowania \texttt{DriveToGoal} (które wchodzi w skład
 sekwencji \texttt{MoveBall} użytej w taktyce \ref{alg:strzelaj})
 przedstawia w sposób uproszczony algorytm \ref{alg:jedzDoCelu}. W
 pierwszej kolejności wyznacza on zachowanie, do którego należy przejść
 w następnym kroku. Jeżeli warunki przejść nie są spełnione, zachowanie
 \texttt{DriveToGoal} będzie wykonane ponownie. Można zauważyć, że możliwe
 zmiany zachowań zależą od aktualnej taktyki oraz szeregu
 heurystycznych ocen (jak np. wartość parametru
 \w{ball\_on\_front}) odnoszących się m. in. do geometrycznych
 relacji między obiektami na boisku.

 \begin{algorithm}[!t]
 \caption{Zachowanie \texttt{DriveToGoal(i)} }
 \label{alg:jedzDoCelu}
 \begin{algorithmic}[1]
 \IF{$SSM_i = $ MoveBall \textbf{and} \w{ball\_on\_front} \textbf{and} \w{can\_kick}}
        \STATE Transition(\w{Kick})
 \ENDIF

 \IF{\w{ball\_on\_front} \textbf{and} \w{ball\_is\_visible}}
        \STATE Transition(\w{GoToBall})
 \ENDIF

 \COMMENT{Command generation}
 \STATE $command_i.navigate \leftarrow true$
 \STATE $command_i.target \leftarrow $ calculateTarget()
 \end{algorithmic}
 \end{algorithm}

 \subsubsection{Plany gry}
 Plany to ostatni element w hierarchii zaproponowanej przez STP.
 Organizują one grę całej drużyny poprzez przydział robotom ról wraz z
 przypisanymi do nich taktykami. Odpowiadają też za synchronizację
 zachowań zawodników na boisku. Typowy plan definiuje:
\begin{itemize}
	\item warunki wykonalności - ich spełnienie jest niezbędne do zastosowania danego planu,
	\item warunki zakończenia - pozwalają stwierdzić, czy nastąpił koniec wykonywania planu,
	\item zestaw ról dla poszczególnych robotów,
	\item szczegóły dotyczące sposobu wykonania planu.
 \end{itemize}

Twórcy STP opracowali specjalny sposób opisu planów w formie, która pozwala na łatwą edycję i jest czytelna dla człowieka. Przykładowy plan przedstawiono na listingu poniżej:
\lstset{language=C++,  basicstyle=\ttfamily\footnotesize, 
	commentstyle={}, xleftmargin=0pt, 
	caption={Przykładowy plan gry zespołu \label{lst:plan1}},
	backgroundcolor=\color{light-gray},
	frame=single,
	breaklines=true}
\begin{lstlisting}
PLAY Naive Offense

APPLICABLE offense

DONE aborted !offense

ROLE 1
shoot A
none

ROLE 2
defend_point {-1400 250} 0 700
none

ROLE 3
defend_lane {B 0 -200} {B 1175 -200}
none

ROLE 4
defend_point {-1400 -250} 0 1400
none
\end{lstlisting}

Pierwsza linia definiuje nazwę planu. Następnie opisane są warunki wykonania zdefiniowane są po słowie kluczowym APPLICABLE. Opierają się one na wysokopoziomowych predykatach generowanych przez moduł analizujący sytuację na boisku. W tym przypadku stosowana jest flaga \w{offense}, która oznacza, że drużyna jest w posiadaniu piłki i atakuje przeciwnika\footnote{W rzeczywistości predykat ten może być oparty na szeregu skomplikowanych obliczeń geometrycznych, historii posiadania piłki przez zespoły, decyzji sędziego itp.}. Podobnie zdefiniowane są warunki zakończenia planu - jedyną różnicę stanowi tutaj fakt, iż po słowie kluczowym DONE występuje jeszcze wartość zwracana jako rezultat działania planu (w tym przypadku \w{aborted}), która może posłużyć jako podstawa np. do decyzji o wyborze tego planu w przyszłości.

Po zdefiniowaniu warunków opisywane są role poszczególnych robotów w danym planie. W przykładzie zdefiniowano role dla czterech robotów (bramkarz jest pomijany). Rola 1 nakazuje użycie taktyki \w{shoot} polegającej na oddaniu strzału na bramkę i zostanie przypisana do robota będącego w posiadaniu piłki. Kolejne role definiują miejsca na boisku, w których powinni znaleźć się pozostali zawodnicy (w tym celu stosowana jest taktyka \w{defend\_point} z odpowiednimi parametrami). Do każdej z ról można przypisać jedną lub więcej taktyk - wtedy wykonywane będą one sekwencyjnie w kolejności zdefiniowanej w planie.

Za realizacją planów odpowiedzialny jest osobny moduł STP. Jego zadaniem jest m. in. przyporządkowanie ról zdefiniowanych w planie poszczególnym robotom. Decyzja o przydziale wynika z taktyk określonych dla danej roli - to właśnie taktyki dostarczają zestaw odpowiednich reguł. Możliwa jest także zamiana ról bez przerywania realizacji planu w momencie zmiany sytuacji na boisku. Ponadto w trakcie gry wykonywane są sprawdzenia prostych akcji, które mogłyby przynieść wymierne zyski dla drużyny. Przykładowo - dla zawodnika posiadającego piłkę sprawdzane jest, czy może on oddać strzał na bramkę z pominięciem aktualnie wykonywanej taktyki. Taki mechanizm zwiększa skuteczność gry zespołu, dodatkowo upraszczając konstrukcję planów, których twórca nie musi uwzględniać takich elementarnych zachowań w ich opisie. Ostatnią rolą wspomnianego modułu jest sprawdzanie warunków zakończenia planu - w tym przypadku dodatkowymi czynnikami są np. decyzje arbitra. Strzelone bramki przekładają się na sukces danego planu, podobnie jak np. rzuty wolne. Natomiast bramki stracone oznaczają porażkę. 

Wyniki zastosowania planów są stosowane podczas decydowania o kolejnych zagraniach. Wybór planów dokonywany jest z kolekcji dostępnych strategii (\w{playbook}). W przypadku, gdy dla danej sytuacji możliwe jest wykonanie tylko jednego planu, wybór wariantu gry jest oczywisty. W momencie, gdy kilka strategii pasuje do warunków na boisku, prawdopodobieństwo wyboru danego planu $P$ związane jest z określoną wagą $w_P$. Wagi te mogą być wcześniej zdefiniowane dla każdego planu, ale możliwe jest także ich modyfikowanie podczas gry na podstawie rezultatów działania danej strategii. Szczegółowo zagadnienie to zostało opisane w \cite{stp_adaptation}.

 \subsection{Planowanie ruchu robota\label{sec:planowanie_ruchu}}


 Umiejętność skutecznej nawigacji w dynamicznym środowisku ligi
 \w{Small Size} jest niezbędna do zbudowania osiągającej sukcesy
 drużyny robotów.
 Analizując dokumentację dostarczoną przez zespoły można zauważyć, iż
 większość rozwiązań opartych jest na metodzie planowania ścieżki
 zwanej \w{RRT} (\w{Rapidly-exploring random trees}). Algorytm ten
 został zaproponowany przez Stevena LaValle \cite{lavalle} w 1998
 roku i od tamtego czasu jest z powodzeniem stosowany w lidze. Starsze
 rozwiązania opierały się na metodzie sztucznych pól potencjału. Oba
 algorytmy zostały szczegółowo opisane poniżej.


 \subsubsection{Metoda sztucznych pól potencjału}


 Metoda ta została początkowo zaproponowana dla manipulatorów
 \cite{andrews}, a następnie zaadaptowana na potrzeby nawigacji
 robotów mobilnych \cite{khatib}. Modeluje ona robota jako punktową
 cząstkę obdarzoną ładunkiem elektrycznym, która porusza się w polu
 potencjału. Przeszkody w otoczeniu robota-cząstki mają ładunek o takim
 samym biegunie, przez co wywierają na niego siłę odpychającą
 pozwalającą na uniknięcie kolizji. Natomiast cel obdarzony jest
 ładunkiem przeciwnym, dzięki czemu robot podąża w zadanym kierunku.
 Zatem wynikowe pole potencjału działające na robota w punkcie
 $q=(x,y)$ jest sumą pól odpychających go od przeszkód $U_p(q)$ oraz
 pola przyciągającego do celu $U_c(q)$:
 \begin{equation}
 U(q)=U_{c}(q) + U_{p}(q)
 \end{equation}
 Zakładając, że funkcja sztucznego pola potencjałowego $U(q)$ jest
 różniczkowalna, siła działająca na robota w punkcie $q=(x,y)$ wyraża
 się wzorem:
 \begin{equation}
 F(q)=-\nabla U(q) = 
\begin{bmatrix}
  \frac{\delta U(q)}{\delta x} \\
  \frac{\delta U(q)}{\delta y} \\
  \end{bmatrix}  
 \end{equation}

\begin{figure}[!t]
\centering
\subfloat[Wynik działania]{\includegraphics[width=0.35\textwidth]{./potencjal} \label{fig:potencjal}}
\hspace{2cm}
\subfloat[Minimum lokalne]{\includegraphics[width=0.35\textwidth]{./potencjal_problem} \label{fig:potencjal_problem}}
\caption{Metoda sztucznych pól potencjału}
\end{figure}

 Potencjał przyciągający jest zazwyczaj modelowany funkcją kwadratową
 \begin{equation}
 U_{c}(q) = \frac{1}{2} \alpha d^2(q,q_c)
 \end{equation}
 gdzie $\alpha$ jest współczynnikiem skalującym, natomiast $d(\cdot)$
 euklidesową odległością pomiędzy aktualną pozycją robota $q$ a pozycją
 docelową $q_{c}$. Siłę przyciągania działającą na robota można wyrazić
 wzorem
 \begin{equation}
 F_c = -\nabla U_c(q) = - \alpha d(q,q_c) \nabla d(q,q_c) = - \alpha (q - q_c)
 \end{equation}
 Siła ta dąży do zera w miarę, jak robot zbliża się do celu.


 Potencjał odpychający modelowany jest za pomocą funkcji rosnącej do
 nieskończoności wraz ze zbliżaniem się do przeszkody:
 \begin{equation}
 U_p(q)=
  \left\{
 \begin{array}{l l}
 \frac{1}{2} \beta \frac{1}{d(q,q_p)^2} & \text{jeśli } d(q,q_p) \leq d_0  \\
 0 & \text{jeśli } d(q,q_p) > d_0   \\
 \end{array} \right.
 \end{equation}
 gdzie $d_0$ oznacza odległość ograniczającą zasięg siły odpychającej
 oddziałującej na robota.

 Wynik działania algorytmu przedstawia rysunek \ref{fig:potencjal}.
 Można zauważyć, że przy odpowiednio dobranych funkcjach potencjału
 robot jest w stanie poruszać się po gładkiej trajektorii do celu.
 Podstawowym problemem związanym ze stosowaniem metody sztucznych pól
 potencjału jest unikanie minimów lokalnych - sytuację taką przedstawia
 rysunek \ref{fig:potencjal_problem}.

\subsubsection{RRT}

 RRT (\w{Rapidly-exploring random tree}) jest stosunkowo prostą metodą
 pozwalającą na szybkie wyznaczenie bezkolizyjnej ścieżki w ciągłej
 przestrzeni otaczającej robota. Algorytm bazuje na eksploracji
 otoczenia za pomocą drzewa możliwych stanów. Jego konstrukcja
 rozpoczyna się od bieżącej pozycji robota. W każdej iteracji z
 prawdopodobieństwem $p$ drzewo rozbudowywane jest w stronę celu.
 Rozbudowa polega na odszukaniu węzła w drzewie znajdującego się
 najbliżej punktu docelowego (stosując np. metrykę euklidesową) i
 dodaniu do niego węzła leżącego w pewnej odległości $d$ w stronę celu.
 Natomiast z prawdopodobieństwem $1-p$ drzewo rozbudowywane jest w
 stronę losowo wybranego (z rozkładem równomiernym) punktu w
 przestrzeni. Dobierając odpowiednią wartość parametru $p$ można
 regulować balans między eksploracją otoczenia a podążaniem w stronę
 celu. Algorytm kończy działanie w momencie, kiedy dodawany węzeł
 znajdzie się w odpowiednio małej odległości od celu. Natomiast
 unikanie kolizji z przeszkodami jest realizowane w ten sposób, że w
 chwili dodawania nowych węzłów do drzewa sprawdzane jest, czy nie
 kolidują one z obiektami w przestrzeni robota. W ten sposób algorytm
 RRT jest w stanie znaleźć bezkolizyjną ścieżkę pozwalającą robotowi
 nawigować w stronę zadanego punktu docelowego.

 Mechanizm budowy drzewa przedstawia rysunek \ref{fig:rrt_schema},
 natomiast przykładowy wynik działania algorytmu pokazano na rysunku
 \ref{fig:rrt_wynik}.  

      \begin{figure}[!h]
      \vspace{1cm}
      \centering
      \includegraphics[width=1\textwidth]{./rrt_schema}
      \caption{Kolejne kroki algorytmu RRT\label{fig:rrt_schema}}
      \end{figure} 
     

        \begin{figure}[ht]
        \vspace{1cm}
        \centering
        \includegraphics[width=0.8\textwidth]{./rrt_result}
        \caption{Ścieżka odnaleziona przez algorytm RRT (źródło: \cite{bruce_veloso})
        \label{fig:rrt_wynik}}
        \end{figure}

\chapter{Zastosowany algorytm sterowania robotem\label{sec:opisAlgorytmu}}

Przegląd rozwiązań stosowanych w lidze \w{Small Size} dokonany w rozdziale \ref{sec:przeglad} posłużył jako punkt wyjścia do projektowania systemu sterowania drużyną zaproponowanego w niniejszej pracy. Z uwagi na fakt, że stworzenie skutecznie grającego zespołu \rc{} jest problemem niezwykle złożonym i często angażującym wieloosobowe zespoły, niezbędne okazały się pewne modyfikacje. Przede wszystkim zdecydowano się na zastąpienie przedstawionego w STP scentralizowanego sterowania grą rozwiązaniem rozproszonym. W tym celu na potrzeby niniejszej pracy stworzono projekt systemu behawioralnego, w którym każdy z robotów jest w stanie samodzielnie wykonywać akcje zapisane w postaci zestawu zadań (odpowiadających taktykom proponowanym przez STP). Gry zespołu nie nadzoruje globalny koordynator, zatem współpraca między zawodnikami wynika tylko z zestawu reguł związanych z aktualnym zadaniem. Tym sposobem zmniejszono złożoność całego systemu - oczywiście kosztem możliwości wykonywania przez zespół skomplikowanych planów wymagających zaawansowanej synchronizacji działań. Rozbudowa systemu o element koordynatora może być rozwiązaniem, które warto wdrożyć podczas dalszych prac nad ligą \w{Small Size}.

        \begin{figure}[!t]
        \centering
        \includegraphics[width=0.95\textwidth]{./architektura_soft}
        \caption{Architektura oprogramowania robota\label{fig:architektura_soft}}
        \end{figure}

Architekturę systemu przedstawiono na rysunku \ref{fig:architektura_soft}. W momencie nadejścia nowych danych (z kamery - o położeniach i prędkościach obiektów na boisku - lub decyzji sędziego) aktualizowany jest blok stanu gry. Jego głównym zadaniem jest gromadzenie oraz przetwarzanie informacje o sytuacji na boisku. Na podstawie danych z kamery oblicza on m.~in. przewidywaną pozycję obiektów. Ponadto dostarcza zestawu predykatów informujących np. o~tym, czy gra jest zatrzymana przez sędziego lub która z drużyn jest w posiadaniu piłki. Na ich podstawie kolejny z bloków - moduł generujący strategię dla robota - dokonuje wyboru odpowiedniego zadania. Zachowanie modułu strategii można konfigurować za pomocą parametrów podawanych do programu robota - decydują one o np. o tym, jaka będzie rola zawodnika na boisku. Z rodzaju wybranego zadania wynikają komendy, jakie są przesyłane do sterownika robota. Przykładem może być polecenie ustawienia robota na zadanej pozycji. W tym celu moduł sterownika komunikuje się z blokiem nawigacyjnym, który wyznacza bezkolizyjną ścieżkę do celu. Na jej podstawie wyznaczane jest odpowiednie sterowanie, które jest przesyłane do zawodnika na boisku.

\section{Zadania\label{sec:zadania}}

Zadania stanowią zestaw algorytmów, w oparciu o które generowania jest strategia zawodnika. Podobnie do taktyk w STP, definiują one warunki wykonalności oraz określają, jakie komendy wraz z parametrami należy wysłać do sterownika robota, aby wykonać zadaną akcję. Lista zadań, jakie opracowano na potrzeby niniejszej pracy, wygląda następująco:

\begin{itemize}
\item \texttt{Stop} - podstawowe zadanie, ustawiające dla robota zerowe wartości prędkości. Stosowane w momencie, kiedy gra jest zatrzymana przez sędziego. Dodatkowo zawodnik wykonujący to zadanie będzie utrzymywać minimalną odległość $50~cm$ od piłki\footnote{Jest to wymóg regulaminu ligi \w{Small Size}}, co pozwala na jej bezproblemowe ustawienie na boisku oraz~wznowienie~gry.

\item \texttt{HoldPosition} - zachowanie polega na utrzymywaniu przez zawodnika zadanej pozycji. Jeżeli miejsce docelowe jest zajęte, robot stara się zbliżyć do niego na minimalną możliwą odległość. Zadanie jest użyteczne w momencie, kiedy sędzia wydał już decyzję o tym, jaki będzie rodzaj wznowienia gry po zatrzymaniu (rzut wolny, rzut rożny itp.) i zawodnik przejął piłkę (będzie wykonywać stały fragment gry), ale nie ma jeszcze prawa podawać, gdyż gra nie została przez arbitra wznowiona. 

\item \texttt{WaitForPass} - zadanie polegające na czekaniu na podanie piłki w zadanym miejscu. Pozycja generowana przez zadanie wynika np. z ról robota lub tzw. obszarów aktywności (opisanych w rozdziale \ref{sec:obszary}). Podczas wykonywania tego zadania robot przemieszcza się do zadanego punktu cały czas pozostając zwróconym w stronę piłki, co poprawia skuteczność odbierania podań lub przechwytywania piłki zgubionej przez innego zawodnika. Jeżeli po dotarciu na miejsce okazuje się, że podanie do robota jest niemożliwe (np. został zasłonięty przez inne roboty), generowany jest nowy punkt docelowy dla zadania.

	\begin{figure}[!b]
	\vspace{0.5cm}
	\centering
	\subfloat[odcięcie od podania]{\includegraphics[width=0.4\textwidth,angle=270]{./krycie2}}
	\hspace{1cm}
	\subfloat[obrona bramki]{\includegraphics[width=0.4\textwidth,angle=270]{./krycie1}}
	\caption{Zadanie krycia przeciwnika - warianty} 
	\label{fig:warianty_krycia}
	\end{figure}

\item \texttt{Cover} - zadanie krycia z góry wyznaczonego przeciwnika, stosowane w sytuacjach defensywnych (gdy drużyna przeciwna posiada piłkę). Robot przemieszcza się do punktu położonego na lini pomiędzy przeciwnikiem a piłką tak, żeby odciąć możliwość podania. W sytuacji, gdy zawodnik, którego wyznaczono do krycia, jest w posiadaniu piłki, robot stara się odciąć możliwość strzału na bramkę. Obie sytuacje przedstawiono na rysunku \ref{fig:warianty_krycia}.

\item \texttt{CaptureBall} - to zachowanie jest stosowane w momencie, kiedy możliwe jest przejęcie piłki. Oznacza to, że istnieje taki punkt leżący na trajektorii ruchu piłki, do którego robot jest w stanie dotrzeć w odpowiednim czasie. Możliwe są tutaj dwa warianty. Pierwszy to kierowanie się do punktu na trajektorii piłki, który jest najbliżej robota. Jest to podejście bezpieczne, ale robot ryzykuje, że inny z zawodników zdąży przejąć piłkę wcześniej. Dlatego zastosowanym podejściem jest wyznaczanie takiego punktu, który pozwoli na jak najszybsze przejęcie poruszającej się piłki. Ilustrację rozwiązania przedstawiono na rysunku~\ref{fig:warianty_przejecia}.

	\begin{figure}[!b]
	\centering
	\subfloat[minimalizacja drogi robota]{\includegraphics[width=0.4\textwidth,angle=0]{./przejecie1}}
	\hspace{1cm}
	\subfloat[minimalizacja czasu przejęcia]{\includegraphics[width=0.4\textwidth,angle=0]{./przejecie2}}
	\caption{Metody przejmowania piłki} 
	\label{fig:warianty_przejecia}
	\end{figure}


\item \texttt{PassTheBall} - zadanie pozwalające na podanie piłki to partnera. Możliwe jest podawanie do najbliższego lub najdalej (w stronę bramki przeciwnika) wysuniętego gracza z zespołu. Aby zadanie było wykonalne, robot musi być w posiadaniu piłki. Do skutecznego podania istotne jest obliczenie z wyprzedzeniem pozycji zawodnika, do którego robot ma podać - pozwala to na przekazywanie sobie piłki przez roboty bez zatrzymywania się.

\item \texttt{Shoot} - zadanie polegające na oddaniu strzału na bramkę. Przed wykonaniem sprawdzane jest, czy istnieje bezkolizyjna droga do bramki. W tym celu należy wykryć, czy żaden z robotów nie znajduje się na linii łączącej piłkę i wybrany punkt w bramce przeciwnika. W celu przyspieszenia procesu sprawdzania testowana jest trajektoria pomiędzy położeniem piłki a $N$ równomiernie rozmieszczonymi punktami położonymi na linii bramkowej. Liczba punktów jest parametrem konfigurowalnym. Rozwiązanie przedstawia rysunek~\ref{fig:strzal}.

        \begin{figure}[!t]
	\vspace{0.5cm}
        \centering
        \includegraphics[width=0.8\textwidth]{./strzal}
        \caption{Sprawdzanie możliwości strzału\label{fig:strzal}}
        \end{figure}

\item \texttt{ProtectGoal} - zachowanie przypisywane zawodnikowi, który pełni rolę bramkarza. Polega ono na takim ustawieniu robota na linii przed bramką, aby blokować przeciwnikom możliwość strzału zasłaniając jak największą część bramki. Zadanie to wykonywane jest zawsze, gdy nie ma możliwości bezpośredniego przechwycenia piłki.

\end{itemize}

\section{Sterownik robota}

Wspomniane w sekcji \ref{sec:zadania} zadania odwołują się do metod, które dostarcza sterownik robota. Stanowią one zestaw elementarnych akcji, które jest w stanie wykonywać zawodnik. Należą do nich:
\begin{itemize}
 \item jazda do zadanej pozycji - akcja przyjmująca jako parametr punkt na planszy, do którego powinien dojechać robot. Odwołuje się ona do bloku nawigacyjnego, który wyznacza ścieżkę do celu. Pierwszy punkt ze ścieżki jest następnie brany jako tymczasowy punkt docelowy i na jego podstawie generowane jest sterowanie, które jest wysyłane do robota.
 \item obrót w stronę celu - akcja, której wykonanie skutkuje zwróceniem robota w stronę zadanego celu. Jej możliwy wariant to obrót z piłką w stronę zadanego punktu - polega on na takim przemieszczaniu się robota, aby piłka pozostała cały czas w tym samym miejscu. 
 \item strzał oraz podanie - obie te akcje pozwalają na ,,kopnięcie'' piłki za pomocą \w{kickera}, w który jest wyposażony robot. Jedyną różnicą jest siła uderzenia - prędkość piłki podczas podania musi być mniejsza, aby zawodnik, do którego skierowano podanie, nie miał problemów z odbiorem.
\end{itemize}

Sterownik umożliwia też zadawanie prędkości liniowej oraz kątowej robota w sposób bezpośredni, co okazuje się być przydatne podczas wykonywania procedur testowych.

\section{Generowanie strategii\label{sec:generowanie_strategii}}

Zadania oraz zestaw elementarnych akcji dostarczanych przez sterownik robota są podstawą działania algorytmu sterującego grą zawodnika. W proponowanym rozwiązaniu sposób powiązania kolejnych zadań oparty jest na automacie skończonym. Stosowane są trzy rodzaje automatu:
\begin{itemize}
 \item sterujący grą bramkarza,
 \item kontrolujący zawodnika podczas zatrzymania gry,
 \item kontrolujący gracza po wznowieniu gry.
\end{itemize}

    \begin{figure}[!t]
    \centering
    \includegraphics[width=0.8\textwidth]{./ai_bramkarz}
    \caption{Strategia sterowania bramkarzem\label{fig:ai_bramkarz}}
    \end{figure}

Rola bramkarza jest zawsze przydzielana jednemu z robotów przed rozpoczęciem meczu (co jest podyktowane zasadami ligi \w {Small Size}). Odpowiadający jej automat skończony przedstawiono na rysunku \ref{fig:ai_bramkarz}. Początkowo zawodnikowi zostaje przydzielone zadanie \texttt{Stop}. Jeżeli sędzia wyda komendę o rozpoczęciu gry (aktualną decyzję sędziego na diagramie reprezentuje zmienna \texttt{cmd}), robot przechodzi do zadania \texttt{ProtectGoal}. W momencie, kiedy możliwe jest przechwycenie piłki i to bramkarz znajduje się najbliżej niej, wykonywane jest zadanie \texttt{CaptureBall}. Po udanym przejęciu bramkarz podaje piłkę do najbardziej wysuniętego partnera z drużyny. Strzelanie nie jest możliwe, jako że strzał przez całe boisko ma niską skuteczność. Należy jeszcze dodać, że każde z zadań może zostać przerwane w momencie, gdy sędzia zatrzyma grę. 

Strategia dla zawodnika grającego w polu jest dużo bardziej skomplikowana. Dlatego dla poprawienia czytelności podzielono algorytm kontrolujący gracza na dwa warianty - sterowanie podczas zatrzymanej gry (rozgrywanie tzw. stałych fragmentów) oraz podczas trwania rozgrywki. Pierwszy z nich zaprezentowano na rysunku~\ref{fig:ai_gracz_stop}. Algorytm rozpoczyna działanie od zadania \texttt{Stop}. Jeżeli to nie drużyna robota wykonuje stały fragment gry, możliwe jest jedno z dwóch zachowań - krycie przeciwnika (jeżeli taka modyfikacja jest włączona - zagadnienie to opisano w sekcji \ref{sec:modyfikacje}) lub czekanie na piłkę w wybranej pozycji defensywnej. W przypadku, gdy sędzia przyznał drużynie robota prawo rozpoczęcia gry, piłkę przejmuje ten z graczy zespołu, który znajduje się najbliżej niej. Po przechwyceniu piłki robot powinien oczekiwać w miejscu (zadanie \texttt{HoldPosition}) na sygnał rozpoczęcia gry (\texttt{cmd == ready}) nadany przez sędziego. Następnie zawodnik może wykonać podanie. 

    \begin{figure}[!t]
    \centering
    \includegraphics[width=0.6\textwidth]{./ai_gracz1}
    \caption{Strategia zawodnika podczas stałego fragmentu gry\label{fig:ai_gracz_stop}}
    \end{figure}

Według zasad ligi \w{Small Size} gra jest uznawana za wznowioną w chwili, w której kopnięta piłka straci kontakt z robotem. W tym momencie moduł generowania strategii otrzymuje odpowiednią informację od komponentu zajmującego się oceną stanu gry i dopóki gra nie zostanie zatrzymana, sterowanie rozgrywką odbywa się według algorytmu przedstawionego na rysunku~\ref{fig:ai_gracz_start}. Stanem początkowym jest zadanie \texttt{HoldPosition}. Jest w nim zawarte większość sprawdzeń związanych z posiadaniem piłki. Jeżeli to robot ma nad nią kontrolę, sprawdzane jest, czy możliwe jest oddanie strzału na bramkę. Jeśli tak, bieżące zadanie zmieniane jest na \texttt{Shoot}. W przeciwnym przypadku robot podejmuje próbę podania do innego zawodnika z drużyny (zadanie \texttt{PassTheBall}). Jeżeli piłka jest już w posiadaniu partnera, robot wychodzi na pozycję, w której będzie oczekiwać na podanie (zadanie \texttt{WaitForPass}). Jeżeli to przeciwnik ma kontrolę nad piłką, robot również wybierze to zadanie (wyznaczając tym razem pozycję defensywną), o ile nie jest włączona funkcja krycia przeciwnika podczas obrony. W sytuacji wykonywania zadań \texttt{WaitForPass} oraz \texttt{Cover} sprawdzane jest dodatkowo, czy nie ma możliwości przejęcia piłki - jeżeli tak, następuje zmiana zadania na \texttt{CaptureTheBall}. Podobnie dzieje się w stanie \texttt{HoldPosition}, jeżeli żaden z zawodników na boisku nie jest w posiadaniu piłki. Wykonywanie wyżej opisanej strategii kończy się w momencie, kiedy gra zostaje przerwana przez sędziego komendą \texttt{halt} lub \texttt{stop}, oznaczającą stały fragment gry.
   
    \begin{figure}[!t]
    \centering
    \includegraphics[width=0.9\textwidth]{./ai_gracz2}
    \caption{Strategia zawodnika podczas trwania gry\label{fig:ai_gracz_start}}
    \end{figure}

Przedstawione powyżej algorytmy zostały dla zachowania czytelności zapisane w sposób uproszczony. W praktyce skuteczny algorytm sterowania wymaga sprawdzania większej liczby warunków. Przykładowo zastosowane zostało rozwiązanie wzorowane na elemencie STP - w momencie wykonywania zadań sprawdzana jest dodatkowo możliwość oddania strzału. Takie pominięcie aktualnego zadania pozwala na zwiększenie skuteczności gry drużyny i lepsze wykorzystywanie okazji do zdobycia bramki. 

Zaproponowane powyżej rozwiązanie pozwala na sterowanie grą pojedynczego robota w środowisku rozproszonym. Nietrudno zauważyć, że dla uproszczenia przyjęto, że wszystkie roboty w danej drużynie posługują się tym samym algorytmem. Dzięki temu można bazować na założeniach, że np. stałe fragmenty gry są zawsze wykonywane przez robota, który znajduje się najbliżej piłki lub rozpoznawać na podstawie położenia względem bramki, który z zawodników pełni rolę bramkarza (jest to przydatne przy wyznaczaniu, do którego zawodnika można podać piłkę). W przypadku, gdy takie założenie nie byłoby spełnione, zaproponowany algorytm mógłby prowadzić do sytuacji konfliktowych. Rozwiązaniem problemu mogłoby być na przykład zaimplementowanie modułu rozpoznającego zadania wykonywane przez partnerów z drużyny. Dane przez niego dostarczone posłużyłyby wtedy jako dodatkowe predykaty w procesie decyzyjnym, poprawiając jakość generowanej strategii.

\section{Modyfikacje strategii\label{sec:modyfikacje}}

Sposób funkcjonowania algorytmu strategii robota może być dodatkowo zmieniany za pomocą parametrów konfiguracyjnych. Mechanizm ten został wprowadzony na potrzeby eksperymentów, które pozwoliłyby ocenić, jakie z funkcji algorytmu mają największy wpływ na wynik meczu. Zdecydowano się na możliwość wykonywania następujących modyfikacji:

\begin{itemize}

\item zdefiniowanie ról dla robotów - domyślnie robotom można przydzielać role bramkarza oraz piłkarza grającego w polu. Zaawansowana modyfikacja polega na podziale graczy pola na atakujących oraz obrońców. Zmiana roli wpływa na pozycje zajmowane przez robota na boisku. Napastnicy będą starali się utrzymać jak najbliżej bramki przeciwnika, natomiast obrońcy będą zajmować pozycje defensywne. Można zatem uznać, że z roli przydzielonej robotowi wynika bezpośrednio jego obszar aktywności na boisku. Więcej szczegółów na temat tego zagadnienia zawarto w sekcji \ref{sec:obszary}.

\item równomierne rozmieszczanie zawodników na boisku - w wersji prostej algorytmu strategii roboty  rozmieszczane są na losowych pozycjach (wybieranych z~rozkładem jednostajnym) w swoich obszarach działania. Zaawansowana modyfikacja polega na dobraniu rozmiarów tych obszarów tak, aby roboty ustawiały się w formacji pokrywającej całą szerokość boiska. Powoduje to rozciągnięcie gry zespołu, co w pewnych sytuacjach daje wymierne korzyści, jak np. zwiększenie szansy na otrzymanie podania.

\item włączenie lub wyłączenie zadania krycia przeciwnika - ostatnia z modyfikowalnych cech. Pozwala ona sprawdzić, jaki wpływ ma umiejętność odcinania przeciwnika od podań podczas obrony na wynik meczu. Wyłączenie tego zadania powoduje, że w sytuacji defensywnej roboty będą zachowywać się tak, jak wynika to z przydzielonych im ról.

\end{itemize}

\section{Obszary aktywności\label{sec:obszary}}

Koncepcja obszarów aktywności to rozwiązanie stworzone po to, aby w prosty sposób opisywać i modyfikować strefę działań zawodnika ligi na boisku. Wspomniany obszar definiuje przestrzeń, z której w sposób losowy wybierane są punkty docelowe dla robota generowane przez zadanie \texttt{WaitForPass}. O tym, w jaki sposób obliczany jest obszar, decydują:

\begin{itemize}
 \item sytuacja na boisku (drużyna atakuje się/broni dostępu do bramki),
 \item rola, jaką przypisano do robota,
 \item stan aktywacji modyfikatora związanego z równomiernym umieszczaniem robotów.
\end{itemize}

W przypadku, gdy roboty nie mają sprecyzowanych ról, używana jest rola domyślna (gracz pola\footnote{Rola bramkarza nie korzysta z obszarów aktywności przy wykonywaniu zadań}). W tej sytuacji obszar aktywności ogranicza się do fragmentu własnej połowy boiska (w przypadku, gdy drużyna się broni) lub połowy przeciwnika - w przypadku ataku (por. rys. \ref{fig:a_domyslne}). Zwężenie obszaru działania podczas obrony ma za zadanie zwiększyć koncentrację robotów pod własną bramką w celu utrudnienia przeciwnikowi oddania skutecznego strzału.

	\begin{figure}[!t]
	\centering
	\subfloat[obrona]{\includegraphics[width=0.45\textwidth]{./a_obrona}}
	\hspace{0.5cm}
	\subfloat[atak]{\includegraphics[width=0.45\textwidth]{./a_atak}}
	\caption{Obszary aktywności zawodników drużyny niebieskiej\\(role domyślne)} 
	\label{fig:a_domyslne}
	\end{figure}

	\begin{figure}[!b]
	\centering
	\subfloat[napastnicy]{\includegraphics[width=0.45\textwidth]{./a_napastnik_atak}}
	\hspace{0.5cm}
	\subfloat[obrońcy]{\includegraphics[width=0.45\textwidth]{./a_obronca_atak}}
	\caption{Obszary aktywności zawodników drużyny niebieskiej podczas ataku (przypisano role 2 napastników oraz 2 obrońców)} 
	\label{fig:a_atak}
	\end{figure}


Jeżeli role zostały określone, napastnicy oraz obrońcy posługują się zupełnie innymi obszarami działania. W przypadku, gdy drużyna atakuje, napastnicy będą starali się utrzymać pozycję pomiędzy bramką przeciwnika a najmniej oddalonym od niej zawodnikiem przeciwników\footnote{Jako, że regulamin nie definiuje sytuacji spalonej, takie zachowanie jest zgodne z zasadami} (ale obszar ten nie może mieć szerokości mniejszej, niż $min$). Obrońcy z kolei będą starali się pozostać w strefie otaczającej najbardziej wysuniętego gracza przeciwnika, aby wspierać napastników, a w razie straty piłki być w stanie szybko wrócić w rejon własnej bramki (rysunek \ref{fig:a_atak}). Natomiast w przypadku, gdy przeciwnik jest w posiadaniu piłki, obszar aktywności obrońców będzie rozciągał się od własnej linii bramkowej do najdalej wysuniętego zawodnika przeciwnika (ale nie może mieć on mniej, niż określono za pomocą parametru $min$). Napastnicy natomiast będą pozostawać w linii z zawodnikami przeciwnika najdalszymi od atakowanej bramki - dzięki temu drużyna broniąca się jest w stanie szybko przejść do ataku (rysunek \ref{fig:a_obrona}).


	\begin{figure}[!t]
	\centering
	\subfloat[obrońcy]{\includegraphics[width=0.45\textwidth]{./a_obronca_obrona}}
	\hspace{0.5cm}
	\subfloat[napastnicy]{\includegraphics[width=0.45\textwidth]{./a_napastnik_obrona}}
	\caption{Obszary aktywności zawodników drużyny niebieskiej \\podczas obrony (przypisano role 2 napastników oraz 2 obrońców)} 
	\label{fig:a_obrona}
	\end{figure}

	\begin{figure}[!b]
	\centering
	\includegraphics[width=0.65\textwidth]{./a_rowne}
	\caption{Przykład równomiernego rozmieszczenia robotów\\ podczas ataku (role domyślne)} 
	\label{fig:a_rowne}
	\end{figure} 

Aktywowanie modyfikatora oznaczającego równomierne rozmieszczenie robotów wpływa na zmianę wysokości obszarów działania zawodników. Ma to swój efekt bez względu na role przypisane robotom. Działanie równomiernego rozmieszczania polega na posortowaniu robotów danej drużyny według rosnącej wartości współrzędnej powstałej z rzutu położenia robota na oś równoległą do linii bramkowej. Tak otrzymana kolejność decyduje o tym, w jaki sposób zostanie zmniejszony aktualny obszar aktywności przydzielony robotowi. Szczegóły tego rozwiązania przedstawiono na rysunku \ref{fig:a_rowne}.


